package com.atwulidun.idivideandconquer02;

import java.util.Random;

// 问题描述：
// 在线性时间O(n)内完成选择，找出一个长度为n的数组中边界为left，right范围内第k小的元素(其中1<=k<=right-left+1)
// 分析：
// 模仿快速排序算法，对数组在left——right范围内进行一次划分（partition方法，我们这里默认采用随机元素为基准），得到基准下标i，不大于基准的在左边，比基准大的在右边。计算出left——i（包含i）中有多少个元素（j），与k进行比较。
// 如果k<j，说明当前left——right中第k小的在左边序列中，那么从left——i-1继续上述步骤寻找第k小。
// 如果k=j，说明基准i就是left——right中第k小，返回a[j]。（因为前面的都不大于它，后面的都大于它，不管左边是序列怎么排的，整体第k（j）小就是它）
// 如果k>j，说明第k小在右边序列，大于基准a[i]，那么从i+1——right继续划分，并将k改为k-j。（整体序列提出了前j个元素，那么第k小在剩下的序列中就是第k-j小了）
// 一直到left=right的时候就可以返回a[left]了
public class RandomizedSelect {
    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 6, 9, 7, 3, 2, 8, 0};
        int value = randomizedSelect(arr, 0, arr.length - 1, 8);
        System.out.println(value);
    }

    public static int randomizedSelect(int[] arr, int left, int right, int k) {
        // 如果一直找不到，直到最后进入到只有一个元素的递归，那么剩下的这个元素肯定是要找的元素，因为肯定能找得到！！！！！！！！
        if (left == right) {
            return arr[left];
        }
        // 以下的index左边的元素都比arr[index]小，右边的元素都比其大
        int index = randomizedPartition(arr, left, right);
        // 获取包括index在内的左边元素的个数
        int leftNo = index - left + 1;
        // 将leftNo和k进行比较
        // 若k小于leftNo，那么在左半区间对k进行递归查询
        if (k < leftNo) {
            return randomizedSelect(arr, left, index - 1, k);
        } else if (k > leftNo) {
            // 若k大于leftNo，那么在右半区间对k进行递归查询，此时变为第k - leftNo小
            return randomizedSelect(arr, index + 1, right, k - leftNo);
        } else {
            // 若k等于leftNo，说明index处的数即为要找的数
            // 注意：这里不能返回坐标，因为这里的index已经是将原来的arr进行调整后的到的，不是对应的原来数组的坐标
            return arr[index];
        }
    }

    private static int randomizedPartition(int[] arr, int left, int right) {
        // 获取left，right范围内的一个随机坐标
        Random random = new Random();
        int ranIndex = random.nextInt(right - left + 1) + left;
        // 在left，right范围内，比arr[ranIndex]小的数都排在其左边，比其大的数都排在其右边
        // 首先将arr[ranIndex]和arr[left]交换位置，类似快速排序的以最左边的一个数为基准数的方法
        swap(arr, left, ranIndex);
        return partition(arr, left, right);
    }

    // 该方法为以最左边的数为基准数，比基准数小的数都排在其左边，比其大的数都排在其右边
    private static int partition(int[] arr, int left, int right) {
        // 把最左边的数设置为基准数
        int base = arr[left];
        // 定义一个左指针
        int i = left;
        // 定义一个右指针
        int j = right;
        // 下面开始进行交换
        while (i != j) {
            // 因为以最左边的数为基准数，因此右指针先往左移动，寻找比基准数小的数
            while (i < j && arr[j] >= base) {
                j--;
            }
            // 左指针往右移动，寻找比基准数大的数
            while (i < j && arr[i] <= base) {
                i++;
            }
            // 将i和j指向的元素进行交换
            swap(arr, i, j);
        }
        // 当i和j相遇时，交换基准数和相遇位置的数
        arr[left] = arr[i];
        arr[i] = base;
        // 返回相遇位置的坐标
        return j;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
